The present invention relates to a method for improving the success of signal routing during the physical synthesis of programmable logic devices.
Various programmable logic architectures are known, including, for example, programmable logic devices (xe2x80x9cPLDsxe2x80x9d), programmable logic arrays (xe2x80x9cPLAsxe2x80x9d), complex programmable logic devices (xe2x80x9cCPLDsxe2x80x9d), field programmable gate arrays (xe2x80x9cFPGAsxe2x80x9d) and programmable array logic (xe2x80x9cPALxe2x80x9d). Although there are differences between these various architectures, each of the architectures typically includes a set of input conductors coupled as inputs to an array of logic gates (e.g., a product term array made up of logical AND gates), the outputs of which, in turn, act as inputs to another portion of the logic device.
Complex Programmable Logic Devices (xe2x80x9cCPLDsxe2x80x9d) are large scale PLDs that, like all programmable architectures, are configured to the specific requirements of an application by programming. A typical programmable logic device consists of one or more logical clusters, each containing one or more logic blocks, one or more memory modules, and an internal bus to carry signals, all connected by one or more Programmable Interconnect Matrices (xe2x80x9cPIMsxe2x80x9d). In some CPLDs, high level channels connect the clusters to each other and to external devices. The connections made in a PIM are determined by routing software.
The signals that need to route to a Logic Block PIM are determined by the desired configuration of the device and the logic inside the logic block. Some of these signals are carried in the top-level horizontal and vertical routing channels that surround the cluster. There are channel-to-cluster PIMs connecting the routing channels to the cluster internal bus. Conventional routing software routes these signals through the channel-to-cluster PIMs, which sends these signals onto a particular set of wires in the cluster bus. Then the routing software routes through the Logic Block PIMs to send the signals into the logic blocks toward their final destination.
Routing of the input set to the output set through a PIM can be defined as a xe2x80x9cMaximum Bipartite Matchingxe2x80x9d problem, and use a standard network-flow based solution. See, for example, the reference entitled xe2x80x9cIntroduction to Algorithmsxe2x80x9d by Cormen, Leiserson and Rivest, 1990 p. 600, which is incorporated herein as background.
The operation of a conventional routing process can best be visualized by reference to conventional art FIGS. 1, 2 and 3. FIG. 1 illustrates a schematic representation of a logical cluster and associated PIMs. Signals 308, carried in channel 206, are selected and routed through channel-to-cluster PIM 205 into cluster 201, then routed by logic block PIM 204 into logic block 255.
The logical operation of a conventional process is illustrated by conventional art FIGS. 2 and 3. Source node 301 represents the set of input signals and input node array 303 represents the arrangement of signals at the PIM input. Note that a PIM is represented here as the combination of input node array set 303, interconnect matrix 305 and output node array set 306. Pathways are determined through interconnect matrix 305 from input to output. The resultant connection graph is illustrated by FIG. 3. The signal present at input node 313 has been successfully routed to output node 316 and the signal present at input node 343 has been successfully routed to output node 336 via pathways 402.
The conventional processes used in the routing software route the signals through a PIM with each signal being routed to exactly one output. In a typical CPLD, the routing software first routes the xe2x80x9cupstreamxe2x80x9d channel-to-cluster PIM 205 (FIG. 1), then the xe2x80x9cdownstreamxe2x80x9d Logic Block PIM 255. Logic block PIM routing is limited to routing a given set of signals represented only once in the set of wires as determined by the routing of the channel-to-cluster PIMs.
In the conventional art, there can be many routing failures because the limited routing resources are not always able to provide a path for all required signals. Typical routing failures occur in routing the Logic Block PIMs inside the cluster. This is due to the nature of the interconnection pattern of the PIM. A given set of signals, each on a particular wire, might not be able to be routed through a PIM since a routing solution for one signal, due to its location in the input set, may use routing resources necessary to the only routing solution available to another signal in the set. The set of input wires the signals occupy are fixed by the routing of the Channel-To-Cluster PIMs. Routing of Channel-To-Cluster PIMs is done without knowing whether Logic Block PIMs downstream can route or not, and this cannot be known at the time the channel-to-cluster PIM is routed. Hence, there is always some probability in the conventional art that a routing solution in the upstream PIM, 205, will induce a routing failure in the downstream PIM, 255. What is required, then, is a method for routing signals in the interconnect matrices of programmable logic devices that reduces the occurrence of routing failures.
A method and system thereof are described herein for routing signals through interconnect matrices in a programmable logic device such that downstream routing failures can be reduced. In one embodiment, the invention is used to improve routing in complex programmable logic devices or CPLDs, however, the invention can be applied to other programmable devices and routing resources.
In routing a set of signals through an upstream interconnect matrix or PIM, the novel method determines a set of high priority signals. The process routes a set of original signals through the upstream PIM so that all signals are routed once and only once. Then the process routes the high priority signals (as many as possible) such that they are duplicated at the output of the upstream PIM. In routing the upstream PIM, the method uses an augmented Maximum Bipartite Matching process (maximum flow) in one embodiment where some signals (high priority signals) are routed twice. Specifically, the high priority signals are re-introduced to existing input nodes of the graph and then path finding steps are performed to locate forward paths through the upstream PIM to additional output nodes, represented in the graph, for the duplicate signals. These duplicated high priority signals are then sent to the input array of the downstream interconnect matrix along with the originally routed signals.
The downstream interconnect matrix can then route the originally routed signals or the duplicate signals depending on position in the input array set and the available routing resources. The method also uses a technique for preventing the simultaneous routing of duplicate signals through the downstream interconnect matrix and ensuring that one, and only one, copy of any signal arrives at the destination output array. Specifically, for each duplicate signal, a virtual node is inserted in a graph between the source node and the input nodes, where the virtual node ensures that each duplicate signal is routed only once. Then, forward paths are determined through the graph to output nodes for each unique signal. Signals are routed once, and only once, this way. The routing failures attendant to conventional routing are thus reduced significantly, if not eliminated.
In one embodiment, the method comprises the steps of selecting highest priority original signals for duplication, routing all signals once through a first interconnect matrix and then routing the duplicated signals through unused pathways remaining in the first interconnect matrix. Then the method includes the steps of routing the signal outputs resulting from the first interconnect matrix through a second interconnect matrix. This second routing comprises the steps of routing all signal outputs, allowing both original and duplicate through the second interconnect matrix and each successfully routed signal is then prevented from being duplicate routed in the second interconnect matrix such that only unique signals are routed, once and only once, through the second interconnect matrix.